

public class IntHashMap {
	
	private class IntEntry {
		final int key;
		int value;
		IntEntry next;

		IntEntry(int k, int v, IntEntry n) {
			value = v;
			next = n;
			key = k;
		}

		public final int getKey() {
			return key;
		}

		public final int getValue() {
			return value;
		}

		public final boolean equals(Object o) {
			if (!(o instanceof IntEntry))
				return false;
			IntEntry e = (IntEntry) o;
			return e.getKey() == key && e.getValue() == e.value;
		}

	}
	
	private class NotFoundKeyException extends RuntimeException {
		private static final long serialVersionUID = 1L;
		public NotFoundKeyException(int key) {
			super(String.valueOf(key));
		}
	}

	/**
	 * The default initial capacity - MUST be a power of two.
	 */
	private static final int DEFAULT_INITIAL_CAPACITY = 16;

	/**
	 * The load factor used when none specified in constructor.
	 */
	private static final float DEFAULT_LOAD_FACTOR = 0.75f;

	/**
	 * The maximum capacity, used if a higher value is implicitly specified by
	 * either of the constructors with arguments. MUST be a power of two <=
	 * 1<<30.
	 */
	private static final int MAXIMUM_CAPACITY = 1 << 30;

	/**
	 * The next size value at which to resize (capacity * load factor).
	 * 
	 * @serial
	 */
	private int threshold;

	/**
	 * The number of key-value mappings contained in this map.
	 */
	private int size;

	/**
	 * The table, resized as necessary. Length MUST Always be a power of two.
	 */
	private IntEntry[] table;

	public IntHashMap() {
		threshold = (int) Math.min(DEFAULT_INITIAL_CAPACITY	* DEFAULT_LOAD_FACTOR, MAXIMUM_CAPACITY + 1);
		table = new IntEntry[DEFAULT_INITIAL_CAPACITY];
	}

	public int get(int key) {
		IntEntry entry = getEntry(key);
		if (entry == null)
			throw new NotFoundKeyException(key);
		return entry.getValue();
	}

	public void put(int key, int value) {
		int hash = hash(key);
		int i = indexFor(hash, table.length);
		for (IntEntry e = table[i]; e != null; e = e.next) {
			if (e.key == key) {
				e.value = value;
				return;
			}
		}

		addEntry(key, value, i);
	}

	/**
	 * Removes the mapping for the specified key from this map if present.
	 * 
	 * @param key
	 *            key whose mapping is to be removed from the map
	 * @return the previous value associated with <tt>key</tt>, or <tt>null</tt>
	 *         if there was no mapping for <tt>key</tt>. (A <tt>null</tt> return
	 *         can also indicate that the map previously associated
	 *         <tt>null</tt> with <tt>key</tt>.)
	 */
    public int remove(int key) {
        IntEntry e = removeEntryForKey(key);
        return (e == null ? null : e.getValue());
    }

	/**
	 * Removes and returns the entry associated with the specified key in the
	 * HashMap. Returns null if the HashMap contains no mapping for this key.
	 */
	private final IntEntry removeEntryForKey(int key) {
		int hash = hash(key);
		int i = indexFor(hash, table.length);
		IntEntry prev = table[i];
		IntEntry e = prev;

		while (e != null) {
			IntEntry next = e.next;
			if (e.key == key) {
				size--;
				if (prev == e)
					table[i] = next;
				else
					prev.next = next;
				return e;
			}
			prev = e;
			e = next;
		}

		return e;
	}

	/**
	 * Retrieve object hash code and applies a supplemental hash function to the
	 * result hash, which defends against poor quality hash functions. This is
	 * critical because HashMap uses power-of-two length hash tables, that
	 * otherwise encounter collisions for hashCodes that do not differ in lower
	 * bits. Note: Null keys always map to hash 0, thus index 0.
	 */
	private final int hash(int k) {
		int h = 0;

		h ^= k;

		// This function ensures that hashCodes that differ only by
		// constant multiples at each bit position have a bounded
		// number of collisions (approximately 8 at default load factor).
		h ^= (h >>> 20) ^ (h >>> 12);
		return h ^ (h >>> 7) ^ (h >>> 4);
	}

	/**
	 * Returns index for hash code h.
	 */
	private static int indexFor(int h, int length) {
		return h & (length - 1);
	}

	/**
	 * Returns <tt>true</tt> if this map contains a mapping for the specified
	 * key.
	 * 
	 * @param key
	 *            The key whose presence in this map is to be tested
	 * @return <tt>true</tt> if this map contains a mapping for the specified
	 *         key.
	 */
	public boolean containsKey(int key) {
		return getEntry(key) != null;
	}

	/**
	 * Returns the entry associated with the specified key in the HashMap.
	 * Returns null if the HashMap contains no mapping for the key.
	 */
	private final IntEntry getEntry(int key) {
		int hash = hash(key);
		for (IntEntry e = table[indexFor(hash, table.length)]; e != null; e = e.next) {
			if (e.key == key)
				return e;
		}
		return null;
	}

	/**
	 * Adds a new entry with the specified key, value and hash code to the
	 * specified bucket. It is the responsibility of this method to resize the
	 * table if appropriate.
	 * 
	 * Subclass overrides this to alter the behavior of put method.
	 */
	private void addEntry(int key, int value, int bucketIndex) {
		if ((size >= threshold) && (null != table[bucketIndex])) {
			resize(2 * table.length);
			int hash = hash(key);
			bucketIndex = indexFor(hash, table.length);
		}

		createEntry(key, value, bucketIndex);
	}

	/**
	 * Like addEntry except that this version is used when creating entries as
	 * part of Map construction or "pseudo-construction" (cloning,
	 * deserialization). This version needn't worry about resizing the table.
	 * 
	 * Subclass overrides this to alter the behavior of HashMap(Map), clone, and
	 * readObject.
	 */
	private void createEntry(int key, int value, int bucketIndex) {
		IntEntry e = table[bucketIndex];
		table[bucketIndex] = new IntEntry(key, value, e);
		size++;
	}

	/**
	 * Rehashes the contents of this map into a new array with a larger
	 * capacity. This method is called automatically when the number of keys in
	 * this map reaches its threshold.
	 * 
	 * If current capacity is MAXIMUM_CAPACITY, this method does not resize the
	 * map, but sets threshold to Integer.MAX_VALUE. This has the effect of
	 * preventing future calls.
	 * 
	 * @param newCapacity
	 *            the new capacity, MUST be a power of two; must be greater than
	 *            current capacity unless current capacity is MAXIMUM_CAPACITY
	 *            (in which case value is irrelevant).
	 */
	private void resize(int newCapacity) {
		IntEntry[] oldTable = table;
		int oldCapacity = oldTable.length;
		if (oldCapacity == MAXIMUM_CAPACITY) {
			threshold = Integer.MAX_VALUE;
			return;
		}

		IntEntry[] newTable = new IntEntry[newCapacity];
		transfer(newTable);
		table = newTable;
		threshold = (int) Math.min(newCapacity * DEFAULT_LOAD_FACTOR,
				MAXIMUM_CAPACITY + 1);
	}

	/**
	 * Transfers all entries from current table to newTable.
	 */
	private void transfer(IntEntry[] newTable) {
		int newCapacity = newTable.length;
		for (IntEntry e : table) {
			while (null != e) {
				IntEntry next = e.next;
				int hash = hash(e.key);
				int i = indexFor(hash, newCapacity);
				e.next = newTable[i];
				newTable[i] = e;
				e = next;
			}
		}
	}

}
